package listnode

func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}
	for len(lists) != 1 {
		node := mergeKLists(lists[0: 2])
		lists = append(lists[2:], node)
	}
	return lists[0]
}

func mergeLists(l1, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}
	if l2 == nil {
		return l1
	}
	p, q := l1, l2
	dummy := &ListNode{}
	l3 := dummy
	for p != nil && q != nil {
		if p.Val < q.Val {
			l3.Next = p
			p = p.Next
		} else {
			l3.Next = q
			q = q.Next
		}
		l3 = l3.Next
	}
	if p != nil {
		l3.Next = p
	}
	if q != nil {
		l3.Next = q
	}
	return dummy.Next
}